package offer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Auther ZhanBo
 * @Date 2020/5/21
 */
public class Solution56 {

    public static void main(String[] args) {
        int [] nums = {4,1,4,6};
        System.out.println(Arrays.toString(singleNumbers3(nums)));
    }

    /**
     * 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
     *
     *输入：nums = [3,4,3,3]
     * 输出：4
     *
     * 输入：nums = [9,1,7,9,7,9,7]
     * 输出：1
     * @param nums
     * @return
     */
    public static int singleNumber(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        Map<Integer,Boolean> map = new HashMap<>();
        for (int item :nums)
            map.put(item, !map.containsKey(item));
        for(int result : nums)
            if (map.get(result))
                return result;
        return -1;
    }


    /**
     *  优化
     * @param nums
     * @return
     */
    public static int singleNumber2(int[] nums) {
        int ones = 0, twos = 0;
        for(int num : nums){
            ones = ones ^ num & ~twos;
            twos = twos ^ num & ~ones;
        }
        return ones;
    }



    /**
     *一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
     *
     * 输入：nums = [4,1,4,6]
     * 输出：[1,6] 或 [6,1]
     *
     * 输入：nums = [1,2,10,4,1,4,3,3]
     * 输出：[2,10] 或 [10,2]
     * @param nums
     * @return
     */
    public static int[] singleNumbers3(int[] nums) {
        int[] result = new int[2];
        int index = 0;
        if (nums.length == 2)
            return nums;
        Map<Integer, Boolean> map = new HashMap<>();
        for (int item : nums)
            map.put(item, !map.containsKey(item));
        for (int item : nums) {
            if(index>=2)
                break;
            else if (map.get(item)) {
                result[index] = item;
                index++;
            }
        }
        return result;
    }
}
